/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/partition-to-k-equal-sum-subsets
   @Language: C++
   @Datetime: 19-04-27 16:14
   */

class Solution {
	bool core(vector<int> &nums, int k, int target, int start, int sum, vector<bool> &vist){
		if(k==0) return true;
		if(target==sum) return core(nums,k-1,target,0,0,vist);
		for(int i=start; i<nums.size(); ++i){
			if(vist[i]) continue;
			vist[i]=true;
			if(core(nums,k,target,i+1,sum+nums[i],vist)) return true;
			vist[i]=false;
		}
		return false;
	}
public:
	/**
	 * @param nums: a list of integer
	 * @param k: an integer
	 * @return: return a boolean, denote whether the array can be divided into k non-empty subsets whose sums are all equal
	 */
	bool partitiontoEqualSumSubsets(vector<int> &nums, int k) {
		// write your code here
		long sum=0;
		for(int i=nums.size(); i--; sum+=nums[i]);
		if(sum%k) return false;
		int target=sum/k;
		vector<bool> vist(nums.size(),false);
		return core(nums,k,target,0,0,vist);
	}
};
